1. Field of the Invention
The present invention relates to a method and an apparatus for employing a tag table and/or an AC table. More particularly, the present invention relates to a method and an apparatus for implementing DCT/IDCT based video/image processing with an aid of a tag table and/or an AC table.
2. Description of the Prior Art
Traditionally, an IDCT decoding method and apparatus perform IDCT decoding process on every incoming DCT data (or also known as DCT coefficient), without checking the content therein. Therefore, even though there are some meaningful contents in the incoming DCT coefficients, no special treatment is made in a traditional IDCT decoding process. Some proposals and amendments have been made to give special treatment on some identified special DCT coefficients, so that some desired effect is gained, such as to reduce the total amount of DCT/IDCT data calculation. Such proposals can be found in the actual product relating to JPEG or MPEG decoding. For the purpose of reducing data calculation, many fast algorithms have been proposed to reduce the amount of data calculation while decoding a DCT coefficient. However, these proposed algorithms still need to process every incoming DCT coefficient, though the amount of data calculation might be reduced within the decoding process of the to-be-processed DCT coefficient. For example, in U.S. Pat. No. 6,167,092, it is proposed that the position of the last non-zero coefficient is utilized to decide which sets of different length 1-D IDCT are to be processed. In U.S. Pat. No. 5,883,823, all the DCT coefficients are categorized into two groups: the first group comprises low-frequency 4×4 DCT coefficients, and the second group comprises other DCT coefficients. The regional IDCT algorithm is performed on all the DCT coefficients in the first group, whether zero or non-zero. The traditional IDCT algorithm is performed on all the other DCT coefficients in the second group. In these two patents, zero and non-zero DCT coefficients are not treated differently, therefore can benefit no advantage due to this valuable distinguishing.
In U.S. Pat. No. 5,576,958, a judgment is imposed on the input port of 1-D IDCT to see whether the incoming DCT coefficient is zero or non-zero. If it is zero, the normally followed multiplication calculation associated with this coefficient can then be omitted. However, this algorithm judges merely one coefficient in one specific time unit. Though the total amount of data calculation can then be reduced, the time spent in the multiplication calculation pertaining to one non-zero DCT coefficient is not reduced. Directly performing 2-D IDCT process, instead of performing 1-D IDCT process twice separately, U.S. Pat. No. 5,636,152 performs IDCT process only on non-zero coefficients. In this algorithm, it can save both the time spent on zero coefficient calculation and the time spent to judge whether the coefficient is zero or non-zero. However, this algorithm benefits at the expense of employing complex circuit structure, such as N×N accumulator and direct 2-D IDCT circuit, and therefore is deemed to be not cost-effective. U.S. Pat. No. 6,421,695 is similar in one aspect with U.S. Pat. No. 5,636,152: it performs IDCT process only on non-zero coefficients. However, it also differs in another aspect with U.S. Pat. No. 5,636,152: it is based on 1-D IDCT structure. As for the input data order in U.S. Pat. No. 6,421,695, there are two kinds: one is zigzag order, and the other is inverse zigzag order. To put the input data in the first zigzag order, the buffer in the input port can be saved, however, the required transpose memory would be very complex. To put the input data in the second inverse zigzag order, the inverse zigzag scanned non-zero input data is first stored in the buffer of the input port. Then, only the non-zero coefficients are calculated according to the position information of the stored input data in the non-zero feeding unit. To employ this algorithm, a large memory would be required to store the position information. Besides, there are few non-zero coefficients while performing the first 1-D IDCT process, whereas there are many more non-zero coefficients while performing the second 1-D DCT process. Because of the aforementioned reason, the efficiency of this algorithm would largely depend on the volume capacity of the transpose memory and the processing capacity of the second 1-ID DCT process.
Please refer to FIG. 1. FIG. 1 shows the block diagram of the data access apparatus 10 in the prior art. In the prior art data access apparatus 10, it receives the bitstream which comprises the data to be decoded in the following IDCT decoding procedure. The apparatus 10 typically comprises a controller 12, a variable length decoder 14, an inverse scan buffer 16, and an inverse quantization circuit 18. The variable length decoder 14 receives the bitstream 20, decodes the data therein and then generates a run information 11 and a level information 13. The run information 11 and the level information 13 are in fact well understood by persons skilled in the DCT/IDCT art. The inverse scan buffer 16 would store the level information 13 and perform zero padding under the control of the controller 12. The inverse quantization circuit 18, also under the control of the controller 12, then receives the content stored in the inverse scan buffer 16 for performing inverse quantization procedure.
Please refer to FIG. 2A and FIG. 2B. FIG. 2A shows the DCT matrix 30 with a plurality of DCT coefficients 32 in a zig-zag scan sequence in the prior art. FIG. 2B shows the inverse scan buffer 16 with a plurality of entries 17 for storing the DCT coefficients and for zero padding in the prior art. The run information is the number of zeros between the present level information and a preceding level information in, for example, a zig-zag scan sequence. Take FIG. 2A as an example, the run information 11 and the level information 13 generated by the variable length decoder 14 are as follows: (run, level)=(0, 1)→(0, 2)→(0, 3)→(2, 4)→(2, 5)→(1, 6)→(3, 7)→EOB (End of block). Here for illustration purpose, the values of the level information are the same as the serial number of the non-zero DCT coefficients.
The level information 13, namely the non-zero DCT coefficients, are temporarily stored in the inverse scan buffer 16 according to their correspondingly precise position in the incoming DCT matrix 30 in the zig-zag scan sequence. When the variable length decoder 14 performs decoding, the non-zero DCT coefficients are generated accordingly and stored in their due entries or positions. The controller 12 would at the same time fill the empty entries, if any, in the inverse scan buffer 16 in order that the correct zig-zag scan sequence of all the DCT coefficients can be reconstructed in later time. This process is also known as “zero padding”. It takes time to perform zero padding in the inverse scan buffer 16. It is particularly time-consuming because the empty entries usually outnumber the occupied entries of non-zero DCT coefficients. Besides, the zero padding is usually performed on every incoming DCT matrix 30. It can be reasonably imagined that the overall data processing time would be longer due to the zero padding process in the apparatus 10. To the worse, all the content, whether non-zero DCT coefficients or later zero-padded entries, temporarily stored in the inverse scan buffer 16 must be sequentially read out to the next stage circuit, for example the inverse quantization circuit 18. It takes longer time to read out all the content stored in the inverse scan buffer 16. It would deteriorate the data processing speed in the apparatus 10 by the extra burden of more accessing times in inverse scan buffer 16. Further, more access times can result in more data read/write errors.
Therefore, the main objective of the present invention is to provide a method and corresponding apparatus for solving the above-mentioned problems, especially with the aids of a tag table. In addition to the aforementioned situation, the tag table can also benefit other applications. Therefore, it is also another objective of the present invention to provide a tag table and/or an AC table to fast assist the determination whether any high frequency DCT coefficient exits in the input DCT block.